1. Field of Invention
The present invention relates generally to computer systems. More particularly, the present invention relates to array element selection with reduced memory consumption.
2. Description of the Related Art
In software applications, data is typically manipulated through the use of various data structures. The data structures selected for a particular software application must provide adequate memory as well as permit efficient retrieval of the data during execution of the application. By way of example, arrays are often used when a predetermined number of data elements are to be processed.
Often, array elements are stored in a predetermined order and are therefore processed consecutively. However, under a variety of circumstances, processing of each array element in an alternate order is preferable. By way of example, each array element may correspond to a particular software process. It may therefore be desirable to change the priority of one or more processes through selecting each process, or array element, in the desired priority order. As yet another example, it may be desirable to process the array in a random order.
When elements in an array are not processed in a consecutive order, it is necessary to maintain a record of the elements that have been selected. Conventional methods typically require the allocation of a second array data structure. By way of example, a corresponding element in a second array of boolean values may be flagged when the array element is selected. As yet another example, a second array or equivalent memory space may be allocated to store each selected element in the array.
Allocating duplicate memory space to process a single array results in inefficient use of available memory. This is particularly problematic in systems with limited data storage space. By way of example, memory space is limited in applications implemented in firmware or embedded systems. Accordingly, it would be desirable if each element in an array could be processed in a non-consecutive order without using a second array or equivalent memory space.
Prior to processing an array, the elements in the array are commonly sorted. One standard sort algorithm that may be used to sort array elements is the "bubble sort" algorithm. According to the "bubble sort" algorithm, adjacent array elements are compared and swapped if they are not in the correct order. In this manner, each pair of adjacent elements is compared and swapped until the smallest (or largest) element "bubbles" to the top of the array. This process is repeated until the entire array is sorted. Thus, since numerous passes are required and multiple pairs of elements must be compared in order to sort the array, this algorithm is inefficient and therefore impractical to implement in most applications. Moreover, this algorithm does not permit an array to be processed and sorted according to any selection criteria. Accordingly, it would be desirable if an array could be sorted and processed according to any order such that each element may be selected and processed without duplication.